#!/usr/bin/env python

class AVLNode:
    def __init__(self, item = None, parent = None, lchild = None, rchild = None, factor = 0):
        '''
        AVL树的节点的初始化函数，其中：
        item：节点中保存的数据，
        rchild:指向右子节点
        lchild:指向左子结点
        parent:指向父节点
        factor:平衡因子
        '''
        self.item = item
        self.lchild = lchild
        self.rchild = rchild
        self.bf = factor
        self.parent = parent
    
    def is_left_child(self):
        '''
        判断是否为父节点的左子树
        '''
        return self.parent is not None and self.parent.lchild == self

    def is_right_child(self):
        '''
        判断是否为父节点的左子树
        '''
        return self.parent is not None and self.parent.rchild == self

    def is_leaf(self):
        '''
        判断是否为叶节点
        '''
        return self.lchild is None and self.rchild is None

    def has_left_child(self):
        '''
        判断是否有左子节点
        '''
        return self.lchild is not None

    def has_right_child(self):
        '''
        判断是否有右子节点
        '''
        return self.rchild is not None

class AVLTree:
    def __init__(self):
        self._root = None
        self._size = 0

    def insert(self, item):
        if self._root is not None:
            self._put(self._root, item)
        else:
            self._root = AVLNode(item)

    def _put(self, node, item):
        if item < node.item:
            if node.has_left_child():
                self._put(node.lchild, item)
            else:
                node.lchild = AVLNode(item, node)
                self.update_balance(node.lchild)
        else:
            if node.has_right_child():
                self._put(node.rchild, item)
            else:
                node.rchild = AVLNode(item, node)
                self.update_balance(node.rchild)

        self._size += 1

    def update_balance(self, node):
        if node.bf > 1 or node.bf < -1:
            self.rebalance(node)
            return
        
        if node.parent != None:
            if node.is_left_child():
                node.parent.bf  += 1
            elif node.is_right_child():
                node.parent.bf -= 1
            
            if node.parent.bf != 0:
                self.update_balance(node.parent)

    def update_balance_delete(self, node):
        if node.bf > 1 or node.bf < -1:
            self.rebalance(node)
            return
        
        if node.parent != None:
            if node.is_left_child():
                node.parent.bf  -= 1
            elif node.is_right_child():
                node.parent.bf += 1
            
            if node.parent.bf != 0:
                self.update_balance(node.parent)
                        
    def rebalance(self, node):
        if nod.bf < 0:
            if node.rchild.bf > 0:
                self.rotate_right(node.rchild)
                self.rotate_left(node)
            else:
                self.rotate_left(node)
        elif node.bf > 0:
            if node.lchild.bf < 0:
                self.rotate_left(node.lchild)
                self.rotate_right(node)
            else:
                self.rotate_right(node)
    
    def rotate_left(self, root):
        new_root = root.rchild
        root.rchild = new_root.lchild
        if new_root.lchild is not None:
            new_root.lchild.parent = root
        
        new_root.parent = root.parent
        if root.parent is None:
            self._root = new_root
        else:
            if root.lchild is not None:
                root.parent.lchild = new_root
            else:
                root.parent.rchild = new_root
        
        new_root.lchild = root
        root.parent = new_root
        root.bf = root.bf + 1 - min(new_root.bf, 0)
        new_root.bf = new_root.bf + 1 + max(root.bf, 0)
    
    def rotate_right(self, root):
        new_root = root.lchild
        root.lchild = new_root.rchild
        if new_root.rchild:
            new_root.rchild.parent = root
        
        new_root.parent = root.parent
        if root.parent is None:
            self._root = new_root
        else:
            if root.parent.rchild is not None:
                root.parent.rchild = new_root
            else:
                root.parent.lchild = new_root

        new_root.rchild = root
        root.parent = new_root
        root.bf = root.bf - 1 - max(new_root.bf, 0)
        new_root.bf = new_root.bf - 1 + min(root.bf, 0)

    def search(self, item):
        cur = self._root

        while cur is not None:
            if cur.item == item:
                break
            elif cur.item > item:
                cur = cur.lchild
            else:
                cur = cur.rchild
        
        return cur

    def find_min(self):
        if self._root is None:
            return None

        cur = self._root
        while cur.lchild is not None:
            cur = cur.lchild

        return cur

    def find_max(self):
        if self._root is None:
            return None

        cur = self._root
        while cur.rchild is not None:
            cur = cur.rchild
        
        return cur

    def delete(self, item):
        # 查找到需要删除的节点
        cur = self.search(item)

        # 没有找到需要删除的节点，直接退出
        if cur is None:
            return

        # 如果找到的节点是根节点
        if self._root == cur:
            # 如果只有一个根节点，直接删除根节点
            if self._root.is_leaf():
                self._root = None
            else:
                # 找出左子树中最小的数据来取代，以符合中序排列
                replace = self.find_min()
                cur.item = replace.item
                replace.parent.lchild = None
                replace.parent.bf -= 1

                if replace == self._root:
                    self._root = self._root.rchild
                else:
                    if replace.parent.is_leaf():
                        self.update_balance_delete(replace.parent)
                    else:
                        self.rotate_left(replace.parent)
        # 如果需要删除的节点为叶节点
        elif cur.is_leaf():
            # 若要删除的节点为其父节点的左子结点，直接删除，并因被删除的是其父节点的左子结点，所以其父节点的平衡因子-1
            if cur.is_left_child():
                cur.parent.lchild = None
                cur.parent.bf -= 1
            # 若要删除的节点为其父节点的右子结点，直接删除，并因被删除的是其父节点的右子节点，所以其父节点的平衡因子+1
            else:
                cur.parent.rchild = None
                cur.parent.bf += 1
            
            # 若删除的节点后，父节点变为叶节点，则其上的节点平衡因子将受到影响，所以必须进行更新
            if cur.parent.is_leaf():
                self.update_balance_delete(cur.parent)
        else:
            if self._root.item > item:
                replace = self.find_min()
                cur.item = replace.item
                replace.parent.lchild = None
                replace.parent.bf -= 1

                if replace.parent.is_leaf():
                    self.update_balance_delete(replace.parent)
                else:
                    self.rotate_left(replace.parent)
            else:
                replace = self.find_max()
                cur.item = replace.item
                replace.parent.rchild = None
                replace.parent.bf += 1

                if replace.parent.is_leaf():
                    self.update_balance_delete(replace.parent)
                else:
                    self.rotate_right(replace.parent)  
        self._size -= 1          
        
    def __delitem__(self, item):
        self.delete(item)

    def __len__(self):
        return self._size

    def size(self):
        return self._size


    
